package sortAlgorithm;

/**
 * 快速排序
 * 
 * @author YNS
 *
 */
public class QuickSort {
	public static int[] sort(int[] source) {
		return quickSort(source, 0, source.length - 1);
	}

	private static int[] quickSort(int[] source, int start, int end) {

		if (start < end) {
			int middleIndex = subQuickSortCore(source, start, end);
			quickSort(source, start, middleIndex - 1);
			quickSort(source, middleIndex + 1, end);
		}

		return source;

	}

	private static int subQuickSortCore(int[] source, int start, int end) {
		int middleValue = source[start];
		while (start < end) {
			while (source[end] >= middleValue && start < end) {
				end--;
			}
			source[start] = source[end];
			while (source[start] <= middleValue && start < end) {
				start++;
			}
			source[end] = source[start];
		}
		source[start] = middleValue;

		return start;
	}
}
